package zoran.wang.graph;

import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * BFS 广度优先搜索，包含了：
 * 1. 层序遍历图（邻接表）的所有节点
 * 2. 层序遍历图（邻接表）的所有节点（带深度）
 * 3. 层序遍历图（邻接表）的所有节点（带深权重）
 * *********************************
 * 4. 层序遍历图（邻接矩阵）的所有节点
 * 5. 层序遍历图（邻接矩阵）的所有节点（带深度）
 * 6. 层序遍历图（邻接矩阵）的所有节点（带权重）
 *
 * @author wangzhuo
 * @time 2025-04-14-22:14
 */
public class LevelOrderTraversal {

    /**
     * 定义：层序遍历图（邻接表）的所有节点
     */
    public void traverseVertex(List<Integer>[] graph) {

        traverseVertex(graph, 0);
    }

    /**
     * 定义：从 vertex 开始层序遍历图（邻接表）的所有节点
     *
     * @param graph
     * @param vertex
     */
    public void traverseVertex(List<Integer>[] graph, int vertex) {

        // visited 防止节点重复遍历
        boolean[] visited = new boolean[graph.length];

        // 借助队列层序遍历
        Queue<Integer> q = new LinkedList<>();
        q.offer(vertex);

        while (!q.isEmpty()) {

            // 出列
            Integer v = q.poll();

            // 排除已经遍历过的节点
            if (visited[v]) continue;

            System.out.print(v + " ");
            visited[v] = true;

            // 遍历相邻节点，没有遍历过的才会放入队列
            for (Integer neighbor : graph[v]) {
                q.offer(neighbor);
            }
        }
    }

    /**
     * 定义：层序遍历图（邻接表）的所有节点
     *
     * @param graph
     */
    public void traverseVertexWithDepth(List<Integer>[] graph) {

        traverseVertexWithDepth(graph, 0);
    }

    /**
     * 定义：从 vertex 开始层序遍历图（邻接表）的所有节点
     *
     * @param graph
     * @param vertex
     */
    public void traverseVertexWithDepth(List<Integer>[] graph, int vertex) {

        // visited 防止节点重复遍历
        boolean[] visited = new boolean[graph.length];

        // 默认节点 0 的深度为 1
        int depth = 1;

        // 借助队列层序遍历
        Queue<Integer> q = new LinkedList<>();
        q.offer(vertex);

        while (!q.isEmpty()) {

            //***********遍历一层***********
            // 获取当前层数的节点数
            int size = q.size();
            for (int i = 0; i < size; i++) {
                // 出列
                Integer v = q.poll();

                // 排除已经遍历过的节点
                if (visited[v]) continue;

                System.out.println(v + " in level " + depth);
                visited[v] = true;

                // 遍历相邻节点，没有遍历过的才会放入队列
                for (Integer neighbor : graph[v]) {
                    q.offer(neighbor);
                }
            }
            //***********遍历一层***********

            depth++;
        }
    }

    // 图结构的 BFS 遍历，从节点 s 开始进行 BFS，且记录路径的权重和
    // 每个节点自行维护 State 类，记录从 s 走来的权重和
    class State {
        // 当前节点 ID
        int node;
        // 从起点 s 到当前节点的权重和
        int weight;

        public State(int node, int weight) {
            this.node = node;
            this.weight = weight;
        }
    }

    /**
     * 带权重的层序遍历
     * TODO:可能写的有问题，但是思路大概是这么个思路
     *
     * @param graph
     * @param vertex
     */
    public void traverseVertexWithWeight(List<Edge>[] graph, int vertex) {

        boolean[] visited = new boolean[graph.length];
        Queue<State> q = new LinkedList<>();

        q.offer(new State(vertex, 0));
        visited[vertex] = true;

        while (!q.isEmpty()) {
            State state = q.poll();
            int cur = state.node;
            int weight = state.weight;
            System.out.println("visit " + cur + " with path weight " + weight);
            for (Edge e : graph[cur]) {
                if (!visited[e.to]) {
                    q.offer(new State(e.to, weight + e.weight));
                    visited[e.to] = true;
                }
            }
        }
    }
}
